//你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单
//元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。 
//
// 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - 
//x1| + |y0 - y1| 。 
//
// 如果网格上只有陆地或者海洋，请返回 -1。 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：[[1,0,1],[0,0,0],[1,0,1]]
//输出：2
//解释： 
//海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。
// 
//
// 示例 2： 
//
// 
//
// 输入：[[1,0,0],[0,0,0],[0,0,0]]
//输出：4
//解释： 
//海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= grid.length == grid[0].length <= 100 
// grid[i][j] 不是 0 就是 1 
// 
// Related Topics 广度优先搜索 图 
// 👍 201 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import sun.awt.image.ImageWatched;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

public class AsFarFromLandAsPossible {
    public static void main(String[] args) {
        Solution solution = new AsFarFromLandAsPossible().new Solution();
        System.out.println(solution.maxDistance(new int[][]{{1, 0,0}, {0, 0, 0}, {0, 0, 0}}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private int[][] grid;

        public int maxDistance(int[][] grid) {
            this.grid = grid;
            int maxLen = -1;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == 0) {
                        maxLen = Math.max(maxLen, findNeast(i, j));
                    }
                }
            }
            return maxLen;
        }

        public int findNeast(int i, int j) {
            Queue<Coordinate> queue = new LinkedList<>();
            int[][] visit = new int[grid.length][grid[0].length];
            int len = 0;
            queue.offer(new Coordinate(i, j));
//            visit[i][j]=1;

            while (!queue.isEmpty()) {

                int size = queue.size();

                for (int k=0;k<size;k++){
                    Coordinate cur = queue.poll();
                    if (cur.x < 0 || cur.x >= grid.length || cur.y < 0 || cur.y >= grid[0].length || visit[cur.x][cur.y]==1 ) {
                        continue;
                    }
                    visit[cur.x][cur.y]=1;
                    if(grid[cur.x][cur.y] == 1){return len;}

                    queue.offer(new Coordinate(cur.x + 1, cur.y));
                    queue.offer(new Coordinate(cur.x - 1, cur.y));
                    queue.offer(new Coordinate(cur.x, cur.y + 1));
                    queue.offer(new Coordinate(cur.x, cur.y - 1));

                }
                len++;
            }
            return -1;
        }

        class Coordinate {
            private int x;
            private int y;

            public Coordinate(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}